We study the problem of load balancing in distributed stream processingengines, which is exacerbated in the presence of skew. We introduce Partial KeyGrouping (PKG), a new stream partitioning scheme that adapts the classical"power of two choices" to a distributed streaming setting by leveraging twonovel techniques: key splitting and local load estimation. In so doing, itachieves better load balancing than key grouping while being more scalable thanshuffle grouping. We test PKG on several large datasets, both real-world andsynthetic. Compared to standard hashing, PKG reduces the load imbalance by upto several orders of magnitude, and often achieves nearly-perfect load balance.This result translates into an improvement of up to 60% in throughput and up to45% in latency when deployed on a real Storm cluster.
展开▼
